CSES - Planets and Kingdoms
  • Time limit: 1.00 s
  • Memory limit: 512 MB

A game has nn planets, connected by mm teleporters. Two planets aa and bb belong to the same kingdom exactly when there is a route both from aa to bb and from bb to aa. Your task is to determine for each planet its kingdom.

Input

The first input line has two integers nn and mm: the number of planets and teleporters. The planets are numbered 1,2,,n1,2,\dots,n.

After this, there are mm lines describing the teleporters. Each line has two integers aa and bb: you can travel from planet aa to planet bb through a teleporter.

Output

First print an integer kk: the number of kingdoms. After this, print for each planet a kingdom label between 11 and kk. You can print any valid solution.

Constraints

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1a,bn1 \le a,b \le n

Example

Input:

5 6
1 2
2 3
3 1
3 4
4 5
5 4

Output:

2
1 1 1 2 2